'''
Contains the governing body and control plane of the network
It holds the traffic engineering mechanism, topology engineering mechanism
also holds all of the routes
'''
import aurora_network, path_selector, cluster_finder, traffic_engineer
import numpy as np
import copy, math

class NetworkController(object):
	# The aurora_network must have already been built by this point
	def __init__(self, aurora_network, toe, te, num_traffic_snapshots):
		self.aurora_network = aurora_network
		self.toe = toe
		self.te = te
		self.num_traffic_snapshots = num_traffic_snapshots
		return 

	def get_output_filename(self):
		dcn_name = self.aurora_network.get_dcn_name()
		toe_param_name = self.toe.get_filename_param()
		te_param_name = self.te.get_filename_param()
		return dcn_name + "_" + toe_param_name + "_" + te_param_name

	def toe_te_class_strings(self):
		toe_string = self.toe.get_string()
		te_string = self.te.get_string()
		return "ToE : {}\nTE : {}\n".format(toe_string, te_string)

	# given a sorted in increascing order topology reconfig timeslots (the timeslot during which we get a new topology)
	# in topology_
	def _recompute_routing_timeslots(self, topology_reconfig_timeslots, te_update_frequency, num_snapshots):
		#print topology_reconfig_timeslots
		topology_reconfig_timeslots = sorted(topology_reconfig_timeslots)
		if topology_reconfig_timeslots[-1] < num_snapshots:
			topology_reconfig_timeslots.append(num_snapshots)
		topology_reconfig_timeslot_index = 0
		curr_time = topology_reconfig_timeslots[topology_reconfig_timeslot_index]
		reroute_timeslots = [curr_time]
		while curr_time < num_snapshots:
			if curr_time + te_update_frequency < topology_reconfig_timeslots[topology_reconfig_timeslot_index + 1]:
				reroute_timeslots.append(curr_time + te_update_frequency)
				curr_time += te_update_frequency
			else:
				reroute_timeslots.append(topology_reconfig_timeslots[topology_reconfig_timeslot_index + 1])
				curr_time = topology_reconfig_timeslots[topology_reconfig_timeslot_index + 1]
				topology_reconfig_timeslot_index += 1
		return reroute_timeslots

	def _compute_link_utilization_statistics(self, nblocks, link_utilization_matrix, adj_matrix):
		total_links = 0.
		lu_distribution = []
		total_weighted_lu = 0.
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					lu_distribution.append( (link_utilization_matrix[i][j], adj_matrix[i][j], ) )
					total_links += adj_matrix[i][j]
					total_weighted_lu += (adj_matrix[i][j] * link_utilization_matrix[i][j])
		lu_distribution_sorted = sorted(lu_distribution, key=lambda x: x[0])	
		cumulative_link_counts = (self.aurora_network.get_total_links() - total_links)
		p50_index = 0.5 * (self.aurora_network.get_total_links())
		p90_index = 0.9 * (self.aurora_network.get_total_links())
		lu50 = -1.
		lu90 = -1.
		mlu = lu_distribution_sorted[-1][0]
		for (lu, num_links) in lu_distribution_sorted:
			if lu50 < 0 and cumulative_link_counts >= p50_index:
				lu50 = lu
			elif lu90 < 0 and cumulative_link_counts >= p90_index:
				lu90 = lu
			cumulative_link_counts += num_links
		alu = total_weighted_lu / total_links
		return (mlu, lu90, lu50, alu, lu_distribution)

	# computes the routing performance for a topology with a given set of routing weights
	# part of static routing
	def _evaluate_snapshot_performance(self, timestamp, traffic_matrix, topology_adj_matrix, routing_weights, return_lu_distribution=False):
		nblocks = len(topology_adj_matrix)
		link_utilization = np.zeros((nblocks, nblocks,))
		hop_counter = 0.
		total_traffic = 0.
		#unable_to_route = False
		for path in routing_weights:
			src = path[0]
			dst = path[-1]
			weight = routing_weights[path]
			if traffic_matrix[src][dst] == 0.:
				continue
			if weight < 0.00001:
				continue
			traffic_load = weight * traffic_matrix[src][dst]
			
			total_traffic += traffic_load
			hop_counter += ((len(path) - 1) * traffic_load)
			curr_node = src
			for index in range(1, len(path), 1):
				next_node = path[index]
				capacity = min(self.aurora_network.get_link_capacity(curr_node), self.aurora_network.get_link_capacity(next_node))
				path_cap = capacity * topology_adj_matrix[curr_node][next_node]
				#if path_cap == 0. and traffic_load >= 0.0001:
					#assert(false)
				if traffic_load / path_cap > 2.:
					print("link_load exploded! from src: {} to dst: {} via path {}".format(src, dst, path))
					print("traffic demand: {} weight : {}, adj_matrix has number of links : {}".format(traffic_matrix[src][dst], weight, topology_adj_matrix[curr_node][next_node]))

				link_utilization[curr_node][next_node] += (traffic_load / path_cap)
				curr_node = next_node
		ave_hop_count = hop_counter / total_traffic
		(mlu, lu90, lu50, alu, lu_distribution) = self._compute_link_utilization_statistics(nblocks, link_utilization, topology_adj_matrix)
		if not return_lu_distribution:
			return (mlu, lu90, lu50, ave_hop_count, timestamp)
		else:
			return (mlu, lu90, lu50, ave_hop_count, timestamp, [x[0] for x in lu_distribution])

	# called externally, 
	#def design_routing_weights_for_timeintervals(self, traffic_snapshots):
	def evaluate_performance(self, traffic_snapshots):
		# do not evaluate if either topology engineer or traffic engineer is empty
		if self.toe is None or self.te is None:
			return None
		assert(len(traffic_snapshots) == self.num_traffic_snapshots)
		print("Evaluating time-series performance.....")
		print("Settings : {}".format(self.toe_te_class_strings()))
		nblocks = self.aurora_network.get_num_blocks()
		time_index = 0
		# get the time intervals during which we would expect a new topology
		topology_intervals = self.toe.get_topology_intervals()
		time_interval_index = 0
		logical_topology_adj_matrix = None
		if len(topology_intervals) > 0:
			(interval_start_time, interval_ending_time) = topology_intervals[time_interval_index]
			logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(0)
		performances = []
		te_class = self.te.traffic_engineering_class()
		num_snapshots = len(traffic_snapshots)
		next_percentage = 0.05
		## Oblivious routing
		if te_class in (traffic_engineer.TrafficEngineeringClass.ECMP, traffic_engineer.TrafficEngineeringClass.WCMP, traffic_engineer.TrafficEngineeringClass.OBLIVIOUS):
			routing_weights = self.te.compute_path_weights(logical_topology_adj_matrix)
			for snapshot in traffic_snapshots:
				traffic_matrix = self.aurora_network.get_traffic_matrix_from_traffic_snapshot(snapshot)
				if time_index > interval_ending_time:
					time_interval_index += 1
					(interval_start_time, interval_ending_time) = topology_intervals[time_interval_index]
					logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(time_index)
					routing_weights = self.te.compute_path_weights(logical_topology_adj_matrix)
				performance = self._evaluate_snapshot_performance(snapshot.time_info.start_time, traffic_matrix, logical_topology_adj_matrix, routing_weights)
				performances.append(performance)
				if float(time_index) / num_snapshots >= next_percentage:
					print("Progress... {}%".format(next_percentage*100))
					next_percentage += 0.05
				time_index += 1
		elif te_class == traffic_engineer.TrafficEngineeringClass.IDEAL:
			for snapshot in traffic_snapshots:
				traffic_matrix = self.aurora_network.get_traffic_matrix_from_traffic_snapshot(snapshot)
				logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(time_index)				
				routing_weights = self.te.compute_path_weights(logical_topology_adj_matrix, traffic_matrix)
				#print("traffic\n{}\n".format(traffic_matrix))
				if routing_weights is None:
					print("logical topology\n{}\n".format(logical_topology_adj_matrix))
				print("time index: {}".format(time_index))
				performance = self._evaluate_snapshot_performance(snapshot.time_info.start_time, traffic_matrix, logical_topology_adj_matrix, routing_weights)
				performances.append(performance)
				if float(time_index) / num_snapshots >= next_percentage:
					print("Progress... {}%".format(next_percentage*100))
					next_percentage += 0.05
				time_index += 1
		elif te_class in (traffic_engineer.TrafficEngineeringClass.ROBUST_TE, traffic_engineer.TrafficEngineeringClass.ROBUST_WEIGHTED_TE):
			## First you might wanna figure out the timeline for traffic engineering. 
			reconfig_length = self.toe.reconfig_length
			te_update_length = self.te.update_frequency
			te_training_length = self.te.training_length
			num_clusters = self.te.get_num_clusters_for_training()
			recompute_routing_timeslots = self._recompute_routing_timeslots(self.toe.get_topology_starting_times(), te_update_length, len(traffic_snapshots))
			recompute_routing_timeslot_index = -1
			routing_weights = None

			for snapshot in traffic_snapshots:
				traffic_matrix = self.aurora_network.get_traffic_matrix_from_traffic_snapshot(snapshot)
				logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(time_index)
				if time_index >= recompute_routing_timeslots[recompute_routing_timeslot_index + 1]:
					recompute_routing_timeslot_index += 1
					training_traffic_points = [np.array(self.aurora_network.get_traffic_vector_from_traffic_snapshot(x, normalize_to=1.)) for x in traffic_snapshots[max(time_index - te_training_length, 0) : time_index]] ## check co
					#print("curr time index : {} training window: {} - {}".format(time_index, max(time_index - te_training_length, 0), time_index - 1))
					#training_traffic_points = [np.array(self.aurora_network.get_traffic_vector_from_traffic_snapshot(x, normalize_to=1.)) for x in traffic_snapshots[time_index : min(time_index + te_update_length, interval_ending_time)]] ## check co
					if len(training_traffic_points) == 0:
						if time_index > 0:
							raise Exception("This should not have happened.")
						#print("time index: {}".format(time_index))
						traffic_point = np.full((nblocks * (nblocks - 1),), 500./(nblocks * (nblocks - 1)))
						training_traffic_points.append(traffic_point)
					#clustering_algo = cluster_finder.ClusteringAlgorithm(len(training_traffic_points), nfeatures=60)
					clustering_algo = cluster_finder.ClusteringAlgorithm(num_clusters, nfeatures=-1)
					traffic_cluster_points = clustering_algo.compute_cluster_centroid(np.array(training_traffic_points))
					centroid_traffic_matrices = [self.aurora_network.normalize_matrix(self.aurora_network.transform_traffic_point_to_traffic_matrix(x), norm=1.) for x in traffic_cluster_points]

					routing_weights = self.te.compute_path_weights(logical_topology_adj_matrix, centroid_traffic_matrices, spare_traffic=0.2)
				#logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(time_index)
				performance = self._evaluate_snapshot_performance(snapshot.time_info.start_time, traffic_matrix, logical_topology_adj_matrix, routing_weights)
				performances.append(performance)
				if float(time_index) / num_snapshots >= next_percentage:
					print("Progress... {}%".format(next_percentage*100))
					next_percentage += 0.05
				time_index += 1
		elif te_class in (traffic_engineer.TrafficEngineeringClass.AVE_TE, traffic_engineer.TrafficEngineeringClass.MAX_TE):
			## First you might wanna figure out the timeline for traffic engineering. 
			reconfig_length = self.toe.reconfig_length
			te_update_length = self.te.update_frequency
			te_training_length = self.te.training_length
			recompute_routing_timeslots = self._recompute_routing_timeslots(self.toe.get_topology_starting_times(), te_update_length, len(traffic_snapshots))
			recompute_routing_timeslot_index = -1
			routing_weights = None
			for snapshot in traffic_snapshots:
				traffic_matrix = self.aurora_network.get_traffic_matrix_from_traffic_snapshot(snapshot)
				if time_index >= recompute_routing_timeslots[recompute_routing_timeslot_index + 1]:
					recompute_routing_timeslot_index += 1
					training_traffic_matrices = [np.array(self.aurora_network.get_traffic_matrix_from_traffic_snapshot(x)) for x in traffic_snapshots[max(time_index - te_training_length, 0) : time_index]] ## check co
					if len(training_traffic_matrices) == 0:
						#print("time index: {}".format(time_index))
						uniform_tm = np.full((nblocks, nblocks,), 50.)
						for i in range(nblocks):
							uniform_tm[i][i] = 0.
						training_traffic_matrices = [uniform_tm, ]
					routing_weights = self.te.compute_path_weights(logical_topology_adj_matrix, training_traffic_matrices)
				logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(time_index)
				performance = self._evaluate_snapshot_performance(snapshot.time_info.start_time, traffic_matrix, logical_topology_adj_matrix, routing_weights)
				performances.append(performance)
				if float(time_index) / num_snapshots >= next_percentage:
					print("Progress... {}%".format(next_percentage*100))
					next_percentage += 0.05
				time_index += 1
		else:
			raise Exception("Unrecognized traffic engineering class of algorithm")
		'''
		elif te_class == traffic_engineer.TrafficEngineeringClass.ROBUST_TE:
			## First you might wanna figure out the timeline for traffic engineering. 
			## TODO (jason) : figure out this one complete this ASAP
			## this is active routing
			reconfig_length = self.toe.reconfig_length
			te_length = self.te.update_frequency
			routing_weights = None
			for snapshot in traffic_snapshots:
				traffic_matrix = self.aurora_network.get_traffic_matrix_from_traffic_snapshot(snapshot)
				trigger_recompute_routing = False
				if time_index > interval_ending_time:
					time_interval_index += 1
					(interval_start_time, interval_ending_time) = topology_intervals[time_interval_index]
					logical_topology_adj_matrix = self.toe.get_logical_topology_at_time(time_index)
					trigger_recompute_routing = True
				# if the topology hasn't changed, check if we are at a time when routing should change
				if not trigger_recompute_routing:
					if (time_index - interval_start_time) % te_length == 0:
						trigger_recompute_routing = True
				if trigger_recompute_routing:
					training_traffic_matrices = [self.aurora_network.get_traffic_matrix_from_traffic_snapshot(x) for x in traffic_snapshots[max(time_index - te_length, 0) : time_index]] ## check co
					if len(training_traffic_matrices) == 0:
						nblocks = self.aurora_network.get_num_blocks()
						for k in range(self.te.get_num_clusters_for_training()):
							tm = np.full((nblocks, nblocks), 50.)
							for i in range(nblocks):
								tm[i][i] = 0.
							training_traffic_matrices.append(tm)
					routing_weights = self.te.compute_path_weights(logical_topology_adj_matrix, training_traffic_matrices)
				performance = self._evaluate_snapshot_performance(traffic_matrix, logical_topology_adj_matrix, routing_weights)
				performances.append(performance)
				time_index += 1
		'''
		return performances

	# evaluates the fat tree performance
	# tapering - the fraction of link counts between the core and aggregation links, must be in range (0, 1]
	def evaluate_fattree_ecmp_performance(self, traffic_snapshots, tapering=1.):
		nblocks = self.aurora_network.get_num_blocks()
		performances = []
		assert(tapering <= 1 and tapering > 0)
		for traffic_snapshot in traffic_snapshots:
			traffic_matrix = self.aurora_network.get_traffic_matrix_from_traffic_snapshot(traffic_snapshot)
			timestamp = traffic_snapshot.time_info.start_time
			link_utilization_vector = []
			avehopcount = 2.
			for src in range(nblocks):
				num_links = math.floor(self.aurora_network.get_num_links(src))
				capacity = self.aurora_network.get_link_capacity(src)
				total_capacity = tapering * num_links * capacity
				total_ingress_traffic = 0.
				total_egress_traffic = 0.
				for dst in range(nblocks):
					if src != dst:
						total_ingress_traffic += traffic_matrix[dst][src]
						total_egress_traffic += traffic_matrix[src][dst]
				link_utilization_vector.append(max(total_egress_traffic / total_capacity, total_ingress_traffic / total_capacity))
			#link_utilization = sorted(link_utilization_vector, key=lambda x: x[0])
			link_utilization = sorted(link_utilization_vector)
			mlu = link_utilization[-1]
			lu90 = link_utilization[int(0.9 * len(link_utilization))]
			lu50 = link_utilization[int(0.5 * len(link_utilization))]
			avehopcount = 2
			perf_tuple = (mlu, lu90, lu50, avehopcount, timestamp)
			performances.append(perf_tuple)
		return performances
